package com.sise.Sort;

/**
 *      二分搜索算法
 *
 *      二分搜索使用的是 while 循环，而不是 递归
 */
public class BinarySearch {

    /**
     *      最基本的二分查找法，局限性：有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2
     */
    public int binarySearch(int[] nums, int target){

        // 将 right 的值为数组长度减一，是为了将左右区间都设置为 闭区间 [left, right]
        int left = 0;
        int right = nums.length - 1;

        // 如果没找到，就需要 while 循环知道区间为空，然后返回 -1。
        // 这里为什么使用的是 left <= right，那么终止条件就是 left == right + 1，带入数据 [3, 2]，此时区间为空
        // 如果使用的是 left < right，那么终止条件就是 left == right，带入数据 [2, 2]，此时的区间不为空，还有数字 2，但 while 循环终止了，故此错误
        while (left <= right){
            int mid = (left + right) >> 1;

            // 当找到数值的时候就停止搜索
            if (mid == target){
                return mid;
            }else if (nums[mid] < target){
                left = mid + 1;
            }else if (nums[mid] > target){
                right = mid - 1;
            }
        }
        return -1;
    }


    /**
     *      寻找左边界的二分搜索
     *      在循环中通过不断的收缩边界，循环结束后得到最接近 target 数值的边界位置，然后再进行边界值的判断：1、是否溢出 2、是否是我们想要的数值
     */
    int left_bound(int[] nums, int target){

        if (nums.length == 0) return -1;

        int left = 0;
        int right = nums.length - 1;

        while (left <= right){
            int mid = left + (right - left) >> 1;       // 防止溢出
            if (nums[mid] == target){
                right = mid - 1;                        // 收缩右侧边界
            }else if (nums[mid] < target){
                left = mid + 1;                         // 搜索区间变为 [mid + 1, right]
            }else if (nums[mid] > target){
                right = mid - 1;                        // 搜索区间变为 [left, mid -1]
            }
        }

        // 由于上面的循环并不会返回，而是不断的收缩边界，此时的 left 是最接近 target 的位置。所以此时需要判断 left 的位置是否溢出，以及是否是我们想要的数字
        if (left >= nums.length || nums[left] != target){
            return -1;
        }
        return left;
    }
}
